#define _CRT_SECURE_NO_WARNINGS 1

//https://leetcode.cn/problems/valid-parentheses/description/

#define MAX_SIZE 10000

typedef struct {
    char data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack* stack) {
    stack->top = -1;
}

bool isEmpty(Stack* stack) {
    return stack->top == -1;
}

bool isFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

void push(Stack* stack, char c) {
    if (isFull(stack)) {
        printf("Stack overflow\n");
    }
    else {
        stack->data[++stack->top] = c;
    }
}

char pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return '\0';
    }
    else {
        return stack->data[stack->top--];
    }
}

bool isValid(char* s) {
    Stack stack;
    initStack(&stack);

    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            push(&stack, s[i]);
        }
        else {
            if (isEmpty(&stack)) {
                return false;
            }
            char left = pop(&stack);
            if ((s[i] == ')' && left != '(') || (s[i] == '}' && left != '{') || (s[i] == ']' && left != '[')) {
                return false;
            }
        }
    }


    return isEmpty(&stack);
}